package com.bootcamp.s2_0922.ds.Exercise._1004_Ex;

/**
 * @program: myClassCode
 * @description: creat my own hashmap
 * @author: Keyu Li
 * @create: 2021-10-04 20:12
 **/

public class Ex4_MyHashMapTest {
    public static void main(String[] args) {
        MyHashMap<Integer, Integer> hashMap = new MyHashMap<>();
        hashMap.put(1, 2);
        hashMap.put(2, 2);
        hashMap.put(3, 2);
        hashMap.put(4, 2);
        hashMap.put(5, 2);

        hashMap.remove(1);
        hashMap.remove(4);

        System.out.println("end");

        MyHashMap<Integer, Integer> hashMap1 = new MyHashMap<>(2);
        MyHashMap<Integer, Integer> hashMap2 = new MyHashMap<>(3);
        System.out.println("");

    }
}

class MyHashMap<K, V> {
    private static final int DEFAULT_INITIAL_CAPACITY = 1 << 2;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    float loadFactor;
    int threshold;
    int size;
    Node[] table;

    class Node<K, V> {
        int hash;
        K key;
        V value;
        Node next;

        public Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    // 默认无参创建hashmap
    public MyHashMap() {
        table = new Node[DEFAULT_INITIAL_CAPACITY];
        loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int) (table.length * loadFactor);
        size = 0;
    }

    // 给定初始容量创建HashMap
    public MyHashMap(int initCapacity) {
        if (initCapacity <= 0) throw new RuntimeException("容量为正整数！");
        table = new Node[getCapacity(initCapacity)];
        loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int) (table.length * loadFactor);
        size = 0;
    }

    private int getCapacity(int initCapacity) {
        int l = initCapacity - 1;
        l = l | (l >> 1);
        l = l | (l >> 2);
        l = l | (l >> 4);
        l = l | (l >> 8);
        l = l | (l >> 16);
        return l < Integer.MAX_VALUE - 8 ? l + 1 : Integer.MAX_VALUE - 8;
    }

    // put添加新节点
    public V put(K key, V value) {
        int hashNew = key.hashCode();
        int index = hashNew % table.length;
        Node p = null, e = table[index];
        while (e != null) {
            if (hashNew == e.hash && (key == e.key || key.equals(e.key))) {
                e.value = value;
                return value;
            }
            p = e;
            e = e.next;
        }
        Node nodeNew = new Node(hashNew, key, value, null);
        if (p == null) {
            table[index] = nodeNew;
        } else
            p.next = nodeNew;
        size++;
        if (size > threshold) resize();
        return value;
    }

    // resize扩容数组
    public boolean resize() {
        int oldCapacity = table.length;
        int newCapacity = getCapacity(oldCapacity + 1);
        if (oldCapacity == newCapacity) throw new RuntimeException("数组长度不能再多了！");
        Node[] newTable = new Node[newCapacity];
        threshold = (int) (newCapacity * loadFactor);

        Node lohead, lotail, hihead, hitail;
        for (int i = 0; i < oldCapacity; i++) {
            Node e = table[i];
            // 判断是否为null
            if (e == null) continue;
            // 分裂链表
            lohead = hihead = lotail = hitail = null;
            while (e != null) {
                if (e.hash % newCapacity == i) {
                    if (lohead == null) lohead = e;
                    else lotail.next = e;
                    lotail = e;
                } else {
                    if (hihead == null) hihead = e;
                    else hitail.next = e;
                    hitail = e;
                }
                e = e.next;
            }
            // 分别放到新位置
            newTable[i] = lohead;
            newTable[i + oldCapacity] = hihead;
        }
        this.table = newTable;
        return true;
    }

    // contains 根据key判断是否存在，返回boolean
    public boolean contains(K key) {
        int hashNew = key.hashCode();
        int index = hashNew % table.length;
        Node e = table[index];
        while (e != null) {
            if (hashNew == e.hash && (key == e.key || key.equals(e.key))) {
                return true;
            }
        }
        return false;
    }

    // get 返回key对应value，如果没找到则返回null（或者value本身为null）
    public V get(K key) {
        int hashNew = key.hashCode();
        int index = hashNew % table.length;
        Node e = table[index];
        while (e != null) {
            if (hashNew == e.hash && (key == e.key || key.equals(e.key))) {
                return (V) e.value;
            }
        }
        return null;
    }

    // remove根据key删除节点,删除成功则返回删除节点value，否则null
    public V remove(K key) {
        int hashNew = key.hashCode();
        int index = hashNew % table.length;
        Node p = null, e = table[index];
        while (e != null) {
            if (hashNew == e.hash && (key == e.key || key.equals(e.key))) {
                if (p == null) {
                    table[index] = null;
                } else {
                    p.next = e.next;
                }
                size--;
                return (V) e.value;
            }
            p = e;
            e = e.next;
        }
        return null;
    }

    // size 获取有效元素个数
    public int size() {
        return size;
    }
}